package leetcode_400;

/**
 *@author 周杨
 *WiggleSubsequence_376 求一个数组最长摇摆序列
 *describe:用动态规划或者贪心算法 AC 100%
 *2018年7月10日 下午4:52:49
 */
public class WiggleSubsequence_376 {

	public static void main(String[] args) {
		WiggleSubsequence_376 test=new WiggleSubsequence_376();
		System.out.println(test.wiggleMaxLength(new int[] {1,7,4,9,2,5}));

	}
	/**
	 * describe:动态规划 时间复杂度O(n^2) 每次就地求出最长增长序列长度和减少序列长度 AC 20%
	 * 2018年7月10日 下午4:06:31
	 */
	public int wiggleMaxLength(int[] nums) {
        if(nums.length==0)
        	return 0;
        int up[]=new int[nums.length];
        int down[]=new int[nums.length];
        up[0]=1;down[0]=1;
        for(int i=1;i<nums.length;++i) {
        	int maxUp=1,maxDown=1;
        	for(int j=0;j<i;++j) {
        		if(nums[i]>nums[j]) {//上升
        			maxUp=Math.max(maxUp, down[j]+1);
        		}
        		else if(nums[i]<nums[j]) {//下降
        			maxDown=Math.max(maxDown, up[j]+1);
        		}
        	}
        	up[i]=maxUp;
        	down[i]=maxDown;
        }
        return Math.max(up[nums.length-1], down[nums.length-1]);
    }
	
	
	 /**
	 * describe:贪心算法 每次保留当前最长升和降的最长长度 在这个点判断是升还是降  AC 100%
	 * 2018年7月10日 下午4:51:53
	 */
	public int wiggleMaxLength1(int[] nums) {
	        if (nums.length == 0) return 0;
	        
	        // 初始思路: 一个2d array，dp[nums][2]  表示 到此处 下降或者是上升的最大长度
	        // 如果这里比前面大： dp[i][1] = dp[i][0] + 1, dp[i][0] = dp[i-1][0], 如果这里是下降的，那么dp[i][0] = dp[i][1] + 1, dp[i][0] = dp[i-1][0],如果相等，二者都不变，array可以简化为两个var
	        int inc = 1;
	        int dec = 1;
	        
	        for (int i = 1; i < nums.length; i++) {
	            
	            if (nums[i] - nums[i-1] > 0) {
	                inc = dec + 1;
	            } else if (nums[i] - nums[i-1] < 0) {
	                dec = inc + 1;
	            }
	        }
	        return Math.max(dec, inc);
	    }
}
